class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> dp(n + 1, vector<bool> (m + 1, false));
        dp[n][m] = true;

        for(int i = m - 1; i >= 0; --i)
            dp[n][i] = i + 1 < m && p[i + 1] == '*' && dp[n][i + 2];

        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = m - 1; j >= 0; --j)
            {
                if(j + 1 == m || p[j + 1] != '*')
                    dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i + 1][j + 1];
                else
                    dp[i][j] = dp[i][j + 2] || ((s[i] == p[j] || p[j] == '.') && dp[i + 1][j]);
            }
        }
        return dp[0][0];

    }

    bool dfs(string& s, string& p, int i, int j)
    {
        if(i == s.size())
        {
            if(j == p.size())
                return true;
            else
                return j + 1 < p.size() && p[j + 1] == '*' && dfs(s, p, i, j + 2);
        }
        else if(j == p.size()) return false;
        else
        {
            if(j + 1 == p.size() || p[j + 1] != '*')
                return (s[i] == p[j] || p[j] == '.') && dfs(s, p, i + 1, j + 1);
            else
            {
                bool res1 = dfs(s, p, i, j + 2);
                bool res2 = (s[i] == p[j] || p[j] == '.') && dfs(s, p, i + 1, j);
                return res1 || res2;
            }
        }
        
    }
};
